0981. 基于时间的键值存储【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 哈希表 + 二分查找

1. 📝 题目描述

• leetcode

设计一个基于时间的键值数据结构，该结构可以在不同时间戳存储对应同一个键的多个值，并针对特定时间戳检索键对应的值。

实现 TimeMap 类：

• TimeMap() 初始化数据结构对象
• void set(String key, String value, int timestamp) 存储给定时间戳 timestamp 时的键 key 和值 value。
• String get(String key, int timestamp) 返回一个值，该值在之前调用了 set，其中 timestamp_prev <= timestamp。如果有多个这样的值，它将返回与最大 timestamp_prev 关联的值。如果没有值，则返回空字符串（""）。

---

示例 1：

输入：
["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]
输出：
[null, null, "bar", "bar", null, "bar2", "bar2"]

解释：
TimeMap timeMap = new TimeMap();
timeMap.set("foo", "bar", 1);  // 存储键 "foo" 和值 "bar"，时间戳 timestamp = 1
timeMap.get("foo", 1);         // 返回 "bar"
timeMap.get("foo", 3);         // 返回 "bar", 因为在时间戳 3 和时间戳 2 处没有对应 "foo" 的值，所以唯一的值位于时间戳 1 处（即 "bar"）。
timeMap.set("foo", "bar2", 4); // 存储键 "foo" 和值 "bar2"，时间戳 timestamp = 4
timeMap.get("foo", 4);         // 返回 "bar2"
timeMap.get("foo", 5);         // 返回 "bar2"

---

提示：

• 1 <= key.length, value.length <= 100
• key 和 value 由小写英文字母和数字组成
• 1 <= timestamp <= 10^7
• set 操作中的时间戳 timestamp 都是严格递增的
• 最多调用 set 和 get 操作 2 * 10^5 次

2. 🎯 s.1 - 哈希表 + 二分查找

js

var TimeMap = function () {
  // key -> [{timestamp, value}, ...]
  this.map = new Map()
}

/**
 * @param {string} key
 * @param {string} value
 * @param {number} timestamp
 * @return {void}
 */
TimeMap.prototype.set = function (key, value, timestamp) {
  if (!this.map.has(key)) {
    this.map.set(key, [])
  }
  // 由于时间戳严格递增，直接 push 即可保持有序
  this.map.get(key).push({ timestamp, value })
}

/**
 * @param {string} key
 * @param {number} timestamp
 * @return {string}
 */
TimeMap.prototype.get = function (key, timestamp) {
  if (!this.map.has(key)) return ''

  const list = this.map.get(key)
  // 二分查找最大的 timestamp_prev <= timestamp
  let left = 0,
    right = list.length - 1,
    result = -1

  while (left <= right) {
    const mid = Math.floor((left + right) / 2)
    if (list[mid].timestamp <= timestamp) {
      result = mid
      left = mid + 1
    } else {
      right = mid - 1
    }
  }

  return result === -1 ? '' : list[result].value
}

/**
 * Your TimeMap object will be instantiated and called as such:
 * var obj = new TimeMap()
 * obj.set(key,value,timestamp)
 * var param_2 = obj.get(key,timestamp)
 */

• 时间复杂度：set 操作 $O(1)$，get 操作 $O(\log n)$，其中 n 是对应键的值的数量
• 空间复杂度：$O(N)$，其中 N 是所有 set 操作的总次数

算法思路：

• 数据结构：使用哈希表存储每个键对应的时间戳-值列表，每个键对应一个数组存储 {timestamp, value} 对象
• set 操作：由于时间戳严格递增，直接将新的时间戳-值对添加到数组末尾即可保持有序
• get 操作：使用二分查找在有序数组中找到小于等于给定时间戳的最大时间戳
• 二分查找：维护 result 记录满足条件的最大索引，当 list[mid].timestamp <= timestamp 时更新 result 并向右搜索
• 边界处理：如果键不存在或找不到满足条件的时间戳，返回空字符串